Serial Attached SCSI (SAS) protocol specifies a protocol stack that provides serial physical interconnect that can be used to connect storage devices such as Hard Disk Drive (HDD) host devices together. It specifies the transport layer protocols to transport SCSI commands, serial ATA (advanced technology attachment) commands and management commands among storage devices. The protocol is intended to be used in conjunction with SCSI and ATA command sets.
The SAS protocol defines the function of an SAS expander device, which is part of the service delivery subsystem and facilitates communication between SAS devices. The switching matrix in a Serial Attached SCSI domain is called an expander, which also provides routing functions. Devices connect to an expander across physical links attached to ports on the device and the expander. In SAS, a physical link is typically a set of four signal lines used as two differential pairs. A “phy” is a transceiver that electrically interfaces with a physical link combined with the portions of the protocol that encode data and manage the reset sequences. A port is created when one or more phys share the same address and attach to a device through one or more physical links.
Multiple SAS end devices and SAS expander devices can be connected together to form a SAS topology. There can be one or multiple physical links connecting each pair of neighbouring devices. When there is a single physical link between two devices, the associated phy on the SAS device is called a narrow port. When there are multiple physical links connecting two devices, the associated phys on an expander are considered to be a wide port. In other words, all links of a wide port are considered to form a common logical link from a routing perspective, although it allows multiple simultaneous connections to pass through the wide port at the same time.
The SAS protocol uses primitive broadcasts to communicate asynchronous events amongst SAS devices. A primitive is fundamentally different from a packet. A packet is typically a multi-byte data structure containing some type of code for delineation of start of packet and end of packet, a header containing address information, data payload and checksum. A broadcast primitive allows different types of messages, with the most common approach in SAS having eight different types of messages, or special control Dwords, that are transmitted into the physical link to communicate up to 8 types of asynchronous events such as topology change. Except for an identification of the type of event, the broadcast primitive does not carry any additional information such as source address, destination address, or time to live.
When a SAS expander receives a broadcast primitive, the primitive is propagated to all the phys of the expander except for the phys on the port that the original broadcast primitive was received from. When an end device receives a broadcast primitive, it notifies the upper layer of the occurrence of the asynchronous event as indicated by the primitive type, but does not propagate the primitive to other physical phys. Thus, whenever a broadcast primitive gets injected to a SAS topology, the primitive will propagate to all devices connected by the topology, including all end devices and expander devices.
An example of SAS topology having a loop is shown in FIG. 1. In this example, the topology contains two levels of expander hierarchies. Two host devices 102 and 104 are connected to expanders 106 and 108, respectively, at the first level of hierarchy. Both expanders 106 and 108 are connected to all three expanders 110, 112 and 114 at the second level hierarchy. Target devices 116 through 126 are connected to one of the three expanders in the second level. The purpose of such a topology is to provide redundancy to protect the system from failures at the first level of the hierarchy. For example, in case of failure of Expander 106, Host 104 can still get access to all target devices through Expander 108.
In FIG. 1, expanders 106 and 108 provide a backplane, while the next level expanders 108, 110 and 112 provide a blade. Multiple disks are attached within the blade.
The dotted line path in FIG. 1 shows one of the loop paths in this topology. Consider a scenario where target 116 loses the physical link to expander 110 Phy 2. Expander 110 Phy2 will detect loss of Dword synchronization and will originate a BROADCAST(CHANGE) primitive, or simply broadcast change primitive. According to standard SAS processing, Expander 110 will send broadcast primitive to all phys except Phy2. In a second step, a broadcast change primitive will be received by Expander 108 Phy1. This causes Expander 108 to send a broadcast change primitive to all phys except Phy1. In a third step, a broadcast change primitive arrives at Expander 112 Phy1, which again propagates the broadcast change primitive to all phys except Phy1.
In a fourth step, the broadcast change primitive is received by Expander 106. Expander 106 sends a broadcast change primitive to all phys except Phy2. Now the broadcast change primitive has got back to Expander 110. Expander 110 will send out a broadcast change primitive again to all phys except Phy0. As shown here, the broadcast change primitive will circulate the loop path continuously and generate a broadcast change primitive on all other phys as it passes through each expander. The broadcast change primitive will flood the entire topology and stay that way indefinitely causing all link bandwidth to be consumed by the broadcast change primitive. The end result is the link bandwidth on the entire topology is consumed by infinite repetition of the broadcast primitive making the topology unusable for transporting data or control traffic. In summary, having a loop in SAS topology causes infinite broadcast storm.
With this in mind, the SAS standard requires that a legal SAS topology cannot contain a loop. In other words, there can be only one logical path (considering all links of a wide port to be a single link) to traverse the topology from any of the devices to any other device. Under such constraints the only type of topology allowed by SAS specification is a tree topology.
A spanning tree of switches used in Ethernet is similar to the required topology of expanders in the SAS standard, i.e. the topology must be loopless. A Bridge Protocol Data Unit (BPDU) in Ethernet is part of the spanning tree protocol that helps describe and identify attributes of a switch port. BPDUs allow for switches to obtain information about each other. If there is any loop in a spanning tree topology, during the topology discovery a BPDU is issued to exchange topology information among switches.
Once a loop is detected in a spanning tree, the switch elects one port to be disabled for all traffic. Therefore, if there is a loop in a spanning tree algorithm based on Ethernet addresses, it identifies a link elected for breakage, i.e. a link that will be entirely disabled. In FIG. 2, this link is identified as 128. Once this link 128 is disabled, it is not only disabled for broadcast traffic but it is disabled for all traffic, as illustrated in FIG. 2.
In the broader field of communications networks, conventional approaches involving broadcast filtering are represented by the following public domain publications, incorporated by reference in their entirety: U.S. Pat. No. 6,556,575 issued Apr. 29, 2003 to Denio et al.; U.S. Pat. No. 5,570,366 issued Oct. 29, 1996 to Baker et al.; U.S. Pat. No. 5,920,699 issued Jul. 6, 1999 to Ballard; Serial Attached SCSI standard revision 1 and revision 1.1; and 802.1D Spanning tree protocol.
Most known techniques teach a filtering method based on packet header information that does not exist in a SAS primitive, hence they can not be applicable or be extended to handle SAS primitive broadcast filtering. Moreover, these conventional techniques do not address the problem of primitive broadcast processing in SAS. Since SAS topologies defined by the SAS standard do not allow for a loop to exist, the problem simply does not exist in a standard compliant SAS environment.
Despite the constraint of the SAS protocol, certain applications demand a redundant path, or a loop, to be supported in the interconnection topology using SAS protocol. Primitive broadcast processing is a challenge in such an environment.
It is, therefore, desirable to provide an approach that solves the broadcast storm problem in SAS topologies with loops.